home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / Headers / Hashtable.h < prev    next >
Text File  |  1999-07-13  |  5KB  |  124 lines
  1. #ifndef _HASHTABLE_
  2. #define _HASHTABLE_
  3.  
  4. #include "Hashable.h"
  5. #include "XPtrList.h"
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12. struct KEntry {
  13.     public:
  14.         unsigned long        mKey;
  15.         const Hashable*        mHashable;
  16.         void*                mValue;
  17.         KEntry*                mNext;            
  18. };
  19.  
  20.  
  21.  
  22.  
  23.     
  24.     
  25. class Hashtable {
  26.  
  27.  
  28.     public:
  29.         // Makes a new Hashtable.  The load factor how efficient memory usage is. The higher
  30.         // the load factor, the more compact the Hashtable it, but at a penalty of performance.
  31.         // In this implementaion, the performance gains out weight the more mem used by 4 or 5 to 1.
  32.         // If inKeysOwned is true, this Hashtable will delete any keys that are of type Hashable when
  33.         // are no longer needed (and on the destruction of this).  For keys added via Put( long, void* ), they
  34.         // are never owned since the keys are actal 4-byte numbers.  For example, a Hashtable used to map
  35.         // ptrs to void*s never owns any keys because the point of using Put( long, void* ) is that the longs used
  36.         // as keys (ie, recast pts) are already unique by nature.
  37.                             Hashtable( bool inKeysOwned = false, int inLoadFactor = 50 );
  38.         virtual                ~Hashtable();
  39.                             
  40.         // Returns the number of entries (ie, key-value pairs) in this hashtable
  41.         inline long         NumEntries() const                                            { return mNumEntries;                                            }
  42.  
  43.         //    Associates inValue with inKey.  
  44.         //    Note: If a value is already assigned to that key, that value is replaced with inValue and
  45.         //            the old value is returned, otherwise NULL is returned.
  46.         //    Note: Values are never owned by a Hashtable--it's the client's responsibilty (they couldn't because they don't know what the long represents!).
  47.         //          Keys are owned by a hashtable depending on what was pass in this' contructor.  
  48.         //    Note: If keys are not owned (see contructor), it's the client's responsibility to (a) delete whatever gets
  49.         //            returned from a Put( Hashable*, void* ) and (b) keep any Hashables currently in this table via Put() 
  50.         //            allocated until this table is deleted/destroyed.
  51.         //    Note: O(1) running time
  52.         inline void*        Put( long                inKey, void* inValue )                { return put( inKey, NULL, inValue );                        }
  53.         inline void*        Put( const Hashable*    inKey, void* inValue )                { return put( inKey->Hash(), inKey, inValue );                }
  54.                 
  55.         //    Fetches the value associated with inKey (from a Put()).   
  56.         //    Note: If a matching key is found, true is returned.  If outValue is NULL, the value is not returned.
  57.         //    Note: O(1) running time
  58.         bool                Get( long                inKey, void** outValue = NULL ) const;
  59.         bool                Get( const Hashable*    inKey, void** outValue = NULL ) const;
  60.  
  61.         //    Returns a list of all the values in this hashtable in no particular order.
  62.         //    Note: The values are added one by one, so the list can have any sorting flag set on it.
  63.         void                GetValues( XPtrList& outValues );
  64.         
  65.         //     Returns a list of all the keys in this hashtable in no particular order
  66.         //    Note: The keys are added one by one, so the list can have any sorting flag set on it.
  67.         void                GetKeys( XPtrList& outKeys );
  68.                 
  69.         //    Return's the nth value in this hashtable, with the values in no particular order. If there 
  70.         //    are less than n entries this this hashtable, NULL is returned.
  71.         //    Note: O(N) running time.
  72.         //void*                Get( long inN );
  73.         
  74.         //     These are 2 other handy ways of invoking Get(long, void**).  The only difference is that if the key isn't
  75.         //    found, it is entered in this dictionary with a value set to zero/NULL.
  76.         void*&                operator[] ( const void* inKey );    
  77.         long&                operator[] ( const long inKey );
  78.         
  79.         //    Removes inKey from this Hashtable.  If inKey is not found, NULL is returned.  
  80.         //    If inKey was found, the key (and its associated value) are removed and the key's value is returned.
  81.         //    Note:  if keys are owned, this fcn deletes the hashable that was used in Put()
  82.         inline void*        Remove( long            inKey )                                { return remove( inKey, NULL );                                }
  83.         inline void*        Remove( const Hashable*    inKey )                                { return remove( inKey -> Hash(), inKey );                    } 
  84.     
  85.         //    Removes/clears all keys in this Dictionary.
  86.         void                RemoveAll();
  87.         
  88.         //    Pre:    The compare function takes in two values and returns if the first is less, equal, or greater than (See XPtrList.h)
  89.         //    Note:    The compare fcn is arbitrary, but if it's it left out (ie. NULL) then it sorts by value size, low to high.
  90.         //    Note:    The compare fcn has the same prototype as the one in XPtrList.h, but this compare fcn is one qsort uses, which
  91.         //            means the void ptrs comin in point to the array elements (not the 4 bytes in the cur pt in the array)
  92.         //    Post:     Get( outKeys[ i ] ) is the ith largest value in this list (in reference to the given compariston fcn)
  93.         //    Post:     outKeys.Count() == inNumToRank  (ie, only inNumToRank values of the ranking are returned)
  94.         //    Note:    If inNumToRank is invalid, the full ranking is returned
  95.         void                Rank( XPtrList& outKeys, CompFunctionT inCompFcn = NULL, long inNumToRank = -1 );
  96.         
  97.     protected:
  98.         void                Rehash();
  99.  
  100.         KEntry*                fetchEntry( long inKey, const Hashable* inHashable ) const;
  101.         void*                remove( long inKey, const Hashable* inHashable );
  102.         void*                put( long inKey, const Hashable* inHashable, void* inValue );
  103.         
  104.         static int            sLongComparitor( const void* inA, const void* inB );
  105.         enum {
  106.             NUM_SIZES        = 15
  107.         };
  108.         
  109.         
  110.         bool                mKeysOwned;
  111.         static long            sTableSizes[ NUM_SIZES ];
  112.  
  113.         KEntry**            mTable;
  114.         unsigned long        mTableSize;
  115.         long                mNumEntries;
  116.         long                mLoadFactor;        // Percent from 0 to 100;
  117.         long                mThreshold;            // Always mLoadFactor * mNumKeys / 100
  118. };
  119.  
  120.  
  121.  
  122.  
  123.  
  124. #endif